Năm 800, Abbasid Caliph Harun al-Rashid đã bổ nhiệm Ibrahim I ibn al-Aghlab, con trai của vị chỉ huy Ả Rập Khurasanian từ bộ lạc Banu Tamim,[6] làm Emir thừa kế của Ifriqiya như một phản ứng với tình trạng hỗn loạn đã trị vì ở tỉnh đó sau sự sụp đổ của Muhallabids. Vào thời điểm đó có lẽ có 100.000 người Ả Rập sống ở Ifriqiya, mặc dù người Berber vẫn chiếm đa số lớn.[7]

Những tín ngưỡng tôn giáo trong đế quốc Byzantine và Ba Tư chuyển đổi mạnh mẽ cuối thế kỷ 6 và đầu thế kỷ 7. Đạo Do Thái là một đức tin cải đạo tích cực, ít nhất một lãnh tụ chính trị người Ả Rập cải sang đạo này.[chú thích 1] Kitô giáo cũng cử những đoàn truyền giáo tích cực cạnh tranh với đạo Zoroastre (Hỏa giáo), đặc biệt nhắm vào người dân ở bán đảo Ả Rập. Những mối quan hệ phức tạp này hội tụ với sự trỗi dậy của đạo Islam (Hồi giáo) ở Arabia dưới thời Mohammed (mất năm 632).[9] Sau cái chết của ông, các đội quân Islam đã chinh phục phần lớn Byzantine và Ba Tư, bắt đầu với Syria năm 634-635, vươn tới Ai Cập năm 640-641, Ba Tư những năm 637-642, Bắc Phi cuối thế kỉ 7. Năm 711, người Hồi giáo vươn tới bán đảo Iberia và tới 714 chiếm phần lớn nơi này, một vùng mà họ gọi là Al-Andalus.[10]

Các cuộc chinh phục của Hồi giáo đạt đến đỉnh điểm vào giữa thế kỉ 8. Sự thất bại của quân Hồi giáo trong Trận Tours năm 732 dẫn đến sự tái chiếm miền nam Pháp bởi người Frank, nhưng thực ra lý do chính của việc Hồi giáo ngừng tấn công châu Âu là cuộc đảo chính lật đổ Khalifah Omeyyad. Triều đại kế tục là Nhà Abbas dời đô tới Bagdad và từ đó bận tâm đến Trung Đông nhiều hơn châu Âu, để mất kiểm soát nhiều vùng đất Hồi giáo. Những con cháu dòng dõi Omeyyad chiếm đóng bán đảo Iberia, nhà Aghlabids kiểm soát Bắc Phi và Nhà Tulun cai trị ở Ai Cập.[11] Đến giữa thế kỉ 8, các tuyến đường giao thương mới nổi lên ở Địa Trung Hải; thương mại giữa người Frank và người Ả Rập thay thế cho các tuyến đường hàng hải của Roma trước kia. Người Frank cung cấp gỗ, lông thú, gươm và cả nô lệ để đổi lại lụa và các loại sợi khác, gia vị, và các kim loại quý từ Ả Rập.[12]